Méthodes basées sur la programmation dynamique

Dans le cadre de l'apprentissage par renforcement, l'utilisation de méthodes de programmation dynamiques permet de calculer les solutions des fonctions de valeurs d'états et d'actions optimales. Cela nous permettra de déterminer par la suite la stratégie que l'agent doit suivre.

Ces méthodes fonctionnent lorsque:

• Le MDP possède un nombre fini et restreint d'états
• Le modèle de l'environnement est parfaitement connu

Nous allons étudier deux algorithmes qui sont:

• L'algorithme par itération des stratégies (Policy Iteration). Cet algorithme comprend deux étapes principales:

  • L'évaluation d'une stratégie (Policy Evaluation)
  • L'amélioration d'une stratégue (Policy Improvement)

• L'algorithme par itération des valeurs (Values Iteration).

5. Algorithme par itération des stratégies

4.4. Algorithme général

Une fois qu'une stratégie $\pi$ a été améliorée en utilisant $V_\pi$ afin d'obtenir une meilleure stratégie $\pi'$, on peut calculer $V_\pi'$ et l'utiliser pour recommencer une procédure d'amélioration sur $\pi'$ afin d'obtenir une stratégie encore plus performante $\pi''$. Chaque stratégie est gratantie d'être une amélioration de toutes les précédentes (à moins qu'elles soient déjà optimales).

Ce processus converge vers une stratégie optimale après quelques itérations. Cette méthode permettant de trouver une stratégie optimale est appellée méthode par itération des stratégies.

Algorithme

On peut remarquer dans l'algorithme ci-dessous que chaque itération d'évaluation d'une stratégie commence avec le résultat de l'évaluation de la précédente stratégie. Cela a pour effet d'améliorer la vitesse de convergence.